package LKGF_STSX;

import java.util.*;

public class String_ {
    public boolean detectCapitalUse(String word) {
        int D1=0;
        int D2=0;
        boolean flg=false;
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(0)>= 'A' && word.charAt(0) <='Z' ){
                flg=true;
            }
            if (word.charAt(i) >= 'A' && word.charAt(i) <='Z'){
                D1++;
            }else {
                D2++;
            }
        }
        if (D1 == 1 && D2 == word.length()-1 && flg){
            return true;
        }else if (D2 == 0 || D1 == 0){
            return true;
        }
        return false;
    }
    public boolean isPalindrome(String s) {

        s=s.toLowerCase();
        StringBuilder stringBuilder=new StringBuilder();
        for (int k = 0; k < s.length(); k++) {
            if ((s.charAt(k) >= 'a' && s.charAt(k) <= 'z')||(s.charAt(k) >= '0' && s.charAt(k) <= '9')){
                stringBuilder.append(s.charAt(k));
            }
        }
        s=stringBuilder.toString();
        int i=0;
        int j=s.length()-1;
        while (i < j){
            if (s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else {
                return false;
            }
        }
        return true;
    }
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
    public int countSegments(String s) {
        int segmentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }


    public String reverseWords(String s) {
        s=s.trim();
       String[] strings=s.split("\\s+");//表示一次性分割1个或多个空格
       // String[] strings=s.split(" ");表示一次分割一个空格
       String ret=new String();
        for (int i = strings.length-1; i >= 0; i--) {
            if (i == 0){
                ret+=strings[i];
            }else {
                ret+=strings[i]+" ";
            }

        }
        return ret;
    }

    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            cnt[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); ++i) {
            char ch = t.charAt(i);
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
    public String frequencySort(String s) {
        char[] cs = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : cs)
            map.put(c, map.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            return a[1] != b[1] ? b[1] - a[1] : a[0] - b[0];
        });
        for (char c : map.keySet())
            q.add(new int[]{c, map.get(c)});

        StringBuilder sb = new StringBuilder();

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int c = poll[0], k = poll[1];
            while (k-- > 0) sb.append((char)(c));
        }

        return sb.toString();
    }



    /**/
    public String originalDigits(String s) {
        Map<Character, Integer> c = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            c.put(ch, c.getOrDefault(ch, 0) + 1);
        }

        int[] cnt = new int[10];
        cnt[0] = c.getOrDefault('z', 0);
        cnt[2] = c.getOrDefault('w', 0);
        cnt[4] = c.getOrDefault('u', 0);
        cnt[6] = c.getOrDefault('x', 0);
        cnt[8] = c.getOrDefault('g', 0);

        cnt[3] = c.getOrDefault('h', 0) - cnt[8];
        cnt[5] = c.getOrDefault('f', 0) - cnt[4];
        cnt[7] = c.getOrDefault('s', 0) - cnt[6];

        cnt[1] = c.getOrDefault('o', 0) - cnt[0] - cnt[2] - cnt[4];

        cnt[9] = c.getOrDefault('i', 0) - cnt[5] - cnt[6] - cnt[8];

        StringBuffer ans = new StringBuffer();
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                ans.append((char) (i + '0'));
            }
        }
        return ans.toString();
    }
    public boolean judgeCircle(String moves) {
        int u=0;
        int d=0;
        int l=0;
        int r=0;

        for (int i = 0; i < moves.length(); i++) {
            char ch=moves.charAt(i);
            if (ch == 'U'){
                u++;
            }else if (ch == 'D'){
                d++;
            }else if (ch == 'L'){
                l++;
            }else {
                r++;
            }
        }
        if (d == u && l == r){
            return true;
        }
        return false;
    }
    public boolean checkRecord(String s) {
        int A=0;
        int L=0;
        int P=0;
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);
            if (ch == 'A'){
                A++;
                L=0;
                if(A >= 2)return false;
            }else if (ch == 'L'){
                L++;
                if(L >= 3)return false;
            }else if (ch == 'P'){
                P++;
                L=0;
            }
        }
        return true;
    }

    public int countBinarySubstrings(String s) {
        List<Integer> counts = new ArrayList<Integer>();
        int ptr = 0, n = s.length();
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            counts.add(count);
        }
        int ans = 0;
        for (int i = 1; i < counts.size(); ++i) {
            ans += Math.min(counts.get(i), counts.get(i - 1));
        }
        return ans;
    }

    public static void main(String[] args) {
        String_ s=new String_();
        s.findSubstringInWraproundString("zab");
    }
    public int findSubstringInWraproundString(String s) {
        String str="abcdefghijklmnopqrstuvwxyz";
        ArrayList<String> arrayList=new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            String ret=new String();
            for (int j = i; j <= i; j++) {
                ret+=s.charAt(j)+"";
            }
            arrayList.add(ret);
        }
        int count=0;
        for (int i = 0; i < arrayList.size(); i++) {
           if (str.contains(arrayList.get(i))){
               count++;
           }
        }
        return count;
    }















}
